QKD methods and systems have been developed which enable two parties to share random data in a way that has a very high probability of detecting any eavesdroppers. This means that if no eavesdroppers are detected, the parties can have a high degree of confidence that the shared random data is secret. QKD methods and systems are described, for example, in U.S. Pat. No. 5,515,438, U.S. Pat. No. 5,999,285 and GB 2427317 A. In many known QKD systems, for example BB84 free-space systems, randomly polarized photons are sent from a transmitting apparatus to a receiving apparatus.
Whatever particular QKD system is used, QKD methods typically involve sending a random data set from a QKD transmitter to a QKD receiver over a quantum signal channel, the QKD transmitter and receiver then respectively processing the data transmitted and received via the quantum signal channel with the aid of messages exchanged between them over an insecure classical communication channel thereby to derive a common subset of the random data set. As the quantum signal channel is a noisy channel, the processing of the data received over that channel includes an error correction phase. However, error correction of the data passed over the quantum signal channel cannot be effected using standard techniques such as the encoding/decoding of the data using linear block codes because only a small percentage of the transmitted photons are ever received. Instead, error correction of the quantum-signal-channel data relies on messages exchanged over the classical channel which is either error free or effectively made so by the use of standard error correction techniques. The classical communication channel need not be secure, as randomization techniques can be used to minimize the information given away. It will be appreciated that even if the classical channel were secure, it does not possess the property of detecting eavesdroppers and therefore cannot substitute for the quantum signal channel.
The present invention relates to techniques for detecting, and preferably correcting, errored bits in a binary data set, these techniques being usable, inter alia, for correcting random data passed over a quantum signal channel.
The use of linear block codes in effecting error correction of data passed over classical communication channels is well known. Briefly, and as depicted in FIG. 1 of the accompanying drawings, a message to be sent over a noisy channel is divided into data blocks m each of k symbols—these symbols are typically binary bits and this will be assumed hereinafter unless otherwise stated. Conveniently each message block can be represented as a row vector m of k bits. Each message block is encoded in encoder 11 into a corresponding n-bit codeword (represented by row vector c) where n>k. The codeword c used is selected from a predetermined set of codewords (the ‘code’ C). For a message block of k bits and a codeword of n bits, the corresponding code C is termed a (n, k) code. After the message block m is encoded as a corresponding codeword c, that codeword is sent by transmitter 13 over the noisy channel 10 and is received at the far end by receiver 14, the output of the receiver being an n-bit received word (represented by row vector r). If no errors are introduced by the transmission over channel 10, the received word r will, of course, correspond to the transmitted codeword c and it is straightforward for decoder 12 to convert the received word r back into the original message block m. Generally, however, the received word r will not correspond to the transmitted codeword c; nevertheless, provided the decoder 12 knows the code C being used by the encoder 1l and the number of errors is limited, it is possible for the decoder 12 to recover the message block m.
Linear block codes are defined by generator and parity-check matrices. In particular, a linear block code C is defined by the null space of its corresponding parity-check matrix H and the product of each codeword c of the code C and the transpose of the parity-check matrix H is the zero vector:c·HT=0
FIG. 2 of the accompanying drawings depicts an example parity check matrix H1 of a (7, 3) linear block code. The code corresponding to the FIG. 2 parity check matrix H1 is of a type referred to as a regular “low density parity check” or “LDPC” code, the name reflecting the fact that the parity check matrix is a sparse matrix and the epithet ‘regular’ indicating that all the rows have the same weight and all the columns also have the same weight. LDPC codes are particularly suitable for use with large message blocks.
The product of the received word r and the transpose of the parity-check matrix is called the error syndrome of r, here represented by vector s:s=r·HT Of course, if the error syndrome s is zero, then the received word r is a codeword c.
Effectively, each row of the parity-check matrix H defines a constraint that must be satisfied by a received word r for it to be judged a valid codeword c. More particularly, each row indicates the bit positions of a received word r whose values must sum to zero, modulo 2 (for binary symbols). Looked at another way, the result of the modulo-2 summation indicated by each row of the parity-check matrix produces a corresponding bit of the error syndrome.
The set of constraints defined by the rows of the parity-check matrix H can be graphically represented by a bipartite graph, known as a Tanner graph, comprising:    a first group of nodes (herein called ‘variable’ nodes and indicated by the letter ‘v’) each corresponding to a respective bit position of an input variable (in the present context the received word r),    a second group of nodes (herein called ‘sum’ nodes and indicated by the non-bold letter s) each corresponding to a respective modulo-2 summation and thus to a respective row of the parity-check matrix, and    edges connecting each sum node s to a respective selection of the variable nodes v, each selection being in accordance with the corresponding row of the parity check matrix.
The values produced at sum nodes s on summing, modulo-2, the values of the connected bit positions of the input variable (received word r) give the error syndrome s. FIG. 3 of the accompanying drawings shows the Tanner graph 15 of the FIG. 2 parity check matrix H1, the graph comprising seven variable nodes 16 (labelled v1 to v7), seven sum nodes 17 (labelled s1 to s7), and edges 18.
It will be appreciated that any given Tanner Graph is characterised by the interconnection of its variable and sum nodes in the network of nodes and edges established by the graph rather than by any particular visual layout of the network; for example, arranging the variable nodes v1 to v7 of the Tanner graph 15 in a different order to that illustrated in FIG. 3, without changing their association to the bit positions of the input variable or the interconnection of each specific variable node to sum nodes, does not change the Tanner graph, merely its visual representation. The representation need not, of course, be visual and, in particular can be a logical representation in a computing environment (for example, lists of nodes indicating their types and linkages to other nodes) and this is to be understood in the following description of the invention wherever a processing system is described as creating or working with a graph.
While the presence of one or more errors in the received word r can be easily determined by checking whether the error syndrome s is non-zero, error correction is more complicated. One error correction method (suitable for use, for example, with LDPC codes) is iterative probabilistic decoding also known as iterative belief propagation or the “Sum-Product” algorithm. A description of this method can be found in various textbooks, for example: “Information Theory, Inference and Learning Algorithms” David J. Mackay, Cambridge University Press, 2003 ISBN 0 521 64298 1, page 559 et seque, herein incorporated by reference—this book is also available on line at: <www.inference.phy.cam.ac.uk/mackay/itila/book.html>
The Sum-Product algorithm is based on a network nodes and edges corresponding to the above-described graphical representation of the constraints defined by the parity-check matrix. More particularly, the Sum-Product algorithm involves each variable node v being initially assigned a probability corresponding to the probability that the corresponding bit of the input variable (received word r) has a particular value (for example, zero). This probability will depend on the error rate of the channel over which the word r was received; for example, if the channel error rate was 0.05, then the probability of a ‘0’ in the received word r actually being ‘0’ is 0.95 whereas the probability of a ‘1’ in the received word r actually being ‘0’ is 0.05.
Each sum node s is assigned an output value corresponding to the value that the sum node will produce when a codeword is presented to the variable nodes; for the above-described context this value is, of course, zero. The ordered set of these values across all the sum nodes is herein termed the “target syndrome” s as it corresponds to the desired value of the error syndrome, that is, the zero vector for the above-described context.
Thereafter, probabilities are exchanged along the edges between the nodes in a series of cycles each of which serves to adjust the probabilities assigned to the variable nodes until convergence is achieved corresponding to variable-node inputs taking on values satisfying the constraints (that is, values that are consistent with the outputs of the sum nodes matching the target syndrome). Each cycle comprises two phases:                In phase 1: messages are sent from each of the variable nodes to the connected sum nodes whereby each sum node is informed of the probability currently assigned to each of its connected variable nodes. Each sum node then determines, for each connected variable node, and on the basis of the assigned output value of the sum node and the probabilities received from the other connected variable nodes, the probability of the concerned variable node having the aforesaid particular value.        In phase 2: messages are sent from each of the sum nodes to the connected variable nodes whereby each variable node is informed of the probabilities currently determined for it by each of its connected sum nodes. Each variable node then assigns itself a new probability based on the probabilities it has received from its connected sum nodes.        
Eventually, the probability at each variable node should converge and stabilize as a probable ‘1’ or ‘0’ indicating the corresponding input value satisfying the constraints set by the graph.
Although the Sum-Product algorithm is described above in terms of probabilities, these probabilities can be represented in a variety of ways besides as straight probabilities; for example it would equally be possible to use log probabilities, or likelihoods/log likelihoods. Reference herein to the probabilities manipulated by the Sum-Product algorithm are to be understood as encompassing such alternative representations.
As noted above, the ‘target syndrome’ will in the context of retrieving the codeword c corresponding to a received word r have a value of zero. However, this need not always be the case. For example, the target syndrome may in fact be the error syndrome itself where the Sum-Product algorithm is used to derive values for the noise vector (see FIG. 47.2c and pages 558, 559 of the above-referenced textbook)